package leetcode_800;

import java.util.Iterator;
import java.util.LinkedList;

/**
 *@author 周杨
 *PrefixAndSuffixSearch_745 实现单词在字典里的前缀后缀搜索
 *describe:用前缀树 AC 76%
 *2018年10月16日 下午2:06:01
 */
public class PrefixAndSuffixSearch_745 {
	private static class Trie {
        TrieNode root;
        
        private Trie() {
            root = new TrieNode();
        }
        
        private void add(String s, int w) {
            TrieNode tmp = root;
            tmp.weights.addFirst(w);
            int i = 0;
            while (i < s.length() && tmp.kids[s.charAt(i)-'a'] != null) {
                tmp = tmp.kids[s.charAt(i)-'a'];
                tmp.weights.addFirst(w);
                i++;
            }
            while (i < s.length()) {
                tmp.kids[s.charAt(i)-'a'] = new TrieNode();
                tmp = tmp.kids[s.charAt(i)-'a'];
                tmp.weights.addFirst(w);
                i++;
            }
        }
        
        private LinkedList<Integer> startsWith(String s) {
            TrieNode tmp = root;
            int i = 0;
            while (i < s.length() && tmp.kids[s.charAt(i)-'a'] != null) {
                tmp = tmp.kids[s.charAt(i)-'a'];
                i++;
            }
            if (i == s.length()) {
                return tmp.weights;
            } else {
                return null;
            }
        }
    }
    
    private static class TrieNode {
        TrieNode[] kids = new TrieNode[26];
        LinkedList<Integer> weights = new LinkedList<Integer>();
        private TrieNode(){
        }
    }
    
    Trie pTrie;
    Trie sTrie;
    
    public PrefixAndSuffixSearch_745(String[] words) {
        pTrie = new Trie();
        sTrie = new Trie();
        for (int i = 0; i < words.length; i++) {
            pTrie.add(words[i], i);
            sTrie.add(new StringBuilder(words[i]).reverse().toString(), i);
        }
    }
    
    public int f(String prefix, String suffix) {
        LinkedList<Integer> pq = pTrie.startsWith(prefix);
        LinkedList<Integer> sq = sTrie.startsWith(new StringBuilder(suffix).reverse().toString());
        return findMaxCommonWeight(pq, sq);
    }
    
    private int findMaxCommonWeight(LinkedList<Integer> w1, LinkedList<Integer> w2) {
        if (w1 == null || w2 == null)
            return -1;
        Iterator<Integer> itr1 = w1.listIterator(0);
        Iterator<Integer> itr2 = w2.listIterator(0);
        Integer first = itr1.next();
        Integer second = itr2.next();
        do {
            if (first.equals(second)) {
                return first;
            } else if (first > second) {
                first = itr1.next();
            } else {
                second = itr2.next();
            }
        } while (first != null && second != null);
        return -1;
    }
}
